package com.example.demo.sort;

/**
 * <pre>
 *  描述:
 * </pre>
 *
 * @author godelgnis(wujiaer)
 * @version 1.0.0
 * @date 2022/1/12 17:40
 */
public class SortPractice0112 extends SortAlgorithmTemplate {
    public static void main(String[] args) {
        new SortPractice0112().run();
    }
    @Override
    protected int[] bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j+1);
                }
            }
        }
        return arr;
    }

    @Override
    protected int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pi = partition(arr, left, right);
            quickSort(arr, left, pi - 1);
            quickSort(arr, pi + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    @Override
    protected int[] simpleInsertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = current;
        }
        return arr;
    }

    @Override
    protected int[] shellSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int len = arr.length;
        for (int step = len / 2; step >= 1; step /= 2) {
            for (int i = step; i < len; i++) {
                int preIndex = i - step;
                int current = arr[i];
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + step] = arr[preIndex];
                    preIndex -= step;
                }
                arr[preIndex+step] = current;
            }
        }
        return arr;

    }

    @Override
    protected int[] simpleSelectSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return arr;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
        return arr;
    }

    @Override
    protected int[] heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int len = arr.length;
        build(arr, len);
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void build(int[] arr, int len) {
        for (int i = len / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIdx = i;
        if (left < len && arr[left] > arr[maxIdx]) {
            maxIdx = left;
        }
        if (right < len && arr[right] > arr[maxIdx]) {
            maxIdx = right;
        }
        if (maxIdx != i) {
            swap(arr, i, maxIdx);
            heapify(arr, maxIdx, len);
        }
    }

    @Override
    protected int[] mergeSort(int[] arr) {
        return new int[0];
    }

    @Override
    protected int[] mergeSortPlus(int[] arr) {
        return new int[0];
    }

    @Override
    protected int[] countSort(int[] arr) {
        return new int[0];
    }

    @Override
    protected int[] bucketSort(int[] arr) {
        return new int[0];
    }

    @Override
    protected int[] radixSort(int[] arr) {
        return new int[0];
    }
}
